package com.wz.leetcode.array;

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix_54 {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0 ||
                matrix[0] == null || matrix[0].length == 0) {
            return result;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int level = Math.min((m+1)/2, (n+1)/2);
        for (int k = 0; k < level; k++) {
            // 从左至右
            for (int j = k; j < n-k; j++) {
                result.add(matrix[k][j]);
            }
            // 从上向下
            for (int i = k + 1; i < m-k; i++) {
                result.add(matrix[i][n-1-k]);
            }
            // 从右至左，当m-1-k == k时，会输出重复
            if (m-1-k > k) {
                for  (int j = n-2-k; j >= k; j--) {
                    result.add(matrix[m-1-k][j]);
                }
            }

            // 从下往上，相等时，会重复输出
            if (k < n-1-k) {
                for (int i = m - 2 - k; i > k; i--) {
                    result.add(matrix[i][k]);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,2,3}, {4,5,6}, {7,8,9}};
        System.out.println(spiralOrder(matrix));
        int[][] matrix1 = new int[][]{{1,2,3}, {4,5,6}};
        System.out.println(spiralOrder(matrix1));
        int[][] matrix2 = new int[][]{{1,2,3}};
        System.out.println(spiralOrder(matrix2));
        int[][] matrix3 = new int[][]{{1}, {2}, {3}};
        System.out.println(spiralOrder(matrix3));
        int[][] matrix4 = new int[][]{{1}};
        System.out.println(spiralOrder(matrix4));
    }
}
